//
// Created by 许欣鑫 on 25-3-27.
//

#ifndef SOLLUTION_2_1_H
#define SOLLUTION_2_1_H
#include <vector>
using namespace std;

class Solution_2_1 {
public:
    //最小路径和 https://leetcode.cn/problems/minimum-path-sum/
    int minPathSum(vector<vector<int> > &grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int> > dp(m + 1, vector<int>(n + 1, INT_MAX));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1 && j == 1) {
                    dp[i][j] = grid[i - 1][j - 1];
                    break;
                }
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

    int minPathSumLessM(vector<vector<int> > &grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<int> dp(n + 1, INT_MAX); // 只使用一个一维数组

        dp[1] = grid[0][0]; // 初始化第一个位置

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i == 1 && j == 1) {
                    dp[j] = grid[i - 1][j - 1];
                } else {
                    dp[j] = min(dp[j], dp[j - 1]) + grid[i - 1][j - 1];
                }
            }
        }

        return dp[n]; // 返回最右下角的值
    }

    //不同路径 https://leetcode.cn/problems/unique-paths/description/
    int uniquePathsDP(int m, int n) {
        vector<int> dp(n, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }

    //不同路径2 https://leetcode.cn/problems/unique-paths-ii/description/
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<int> dp(n, 0);
        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 1; i < n; i++) {
            dp[i] = (obstacleGrid[0][i] == 0 && dp[i - 1] != 0) ? 1 : 0;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                    continue;
                }
                if (j > 0)
                    dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
};
#endif //SOLLUTION_2_1_H
